{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cf411d0b",
   "metadata": {},
   "source": [
    "## 1. 单调栈介绍"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e294cdfc",
   "metadata": {},
   "source": [
    "### 1.1 参考\n",
    "- [[数据结构]——单调栈](https://blog.csdn.net/lucky52529/article/details/89155694)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e829587",
   "metadata": {},
   "source": [
    "### 1.2 具体描述\n",
    "- 概念：单调栈，对应即包含单调递增栈和单调递减栈，即栈重数据是有顺序的\n",
    "  - 单调递增栈：栈底 -> 栈顶, 数据是从大 -> 小\n",
    "  - 单调递减栈：栈底 -> 栈顶，数据是从小 -> 大\n",
    "\n",
    "- Demo：模拟一个单调递增栈\n",
    " > 1. 现在有一组数10，3，7，4，12。从左到右依次入栈;  \n",
    " > 2. 如果栈为空或入栈元素值小于栈顶元素值，则入栈；  \n",
    " > 3. 否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0bef54af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input: [10, 2, 4, 5, 2, 6]\n",
      "res: []\n",
      "res: [10]\n",
      "res: [10, 2]\n",
      "temp ---: [2]\n",
      "temp ===: [2]\n",
      "*****: [10, 4, 2]\n",
      "res: [10, 4, 2]\n",
      "temp ---: [2]\n",
      "temp ---: [2, 4]\n",
      "temp ===: [4, 2]\n",
      "*****: [10, 5, 4, 2]\n",
      "res: [10, 5, 4, 2]\n",
      "res: [10, 5, 4, 2, 2]\n",
      "temp ---: [2]\n",
      "temp ---: [2, 2]\n",
      "temp ---: [2, 2, 4]\n",
      "temp ---: [2, 2, 4, 5]\n",
      "temp ===: [5, 4, 2, 2]\n",
      "*****: [10, 6, 5, 4, 2, 2]\n",
      "processed: [10, 6, 5, 4, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "# 解题思路:\n",
    "# 结果存入list 中，如果遇到比栈顶的值还大的，因该值需要插入到合适位置，所以须将比该值小的全部pop出来存入到临时的list中\n",
    "# 当遇到了比当前值大的栈元素时，则在此位置将该值插入，并将之前pop出来的，塞回去\n",
    "# 用到的list操作，listV.append(a)   b = listV.pop()   listV.reverse() \n",
    "def stack_increase(a):\n",
    "    # require input be a list, print the sorted list\n",
    "    print(\"input:\", a)\n",
    "    res = []\n",
    "    for item in a:\n",
    "        print(\"res:\", res)\n",
    "        if len(res) == 0 or item <= res[-1]:\n",
    "            res.append(item)\n",
    "        else:\n",
    "            temp = []\n",
    "            length = len(res)\n",
    "            for i in range(length):\n",
    "                if res[length -1 -i] < item:\n",
    "                    temp.append(res.pop())\n",
    "                    print(\"temp ---:\", temp)\n",
    "            res.append(item)\n",
    "            temp.reverse()\n",
    "            print(\"temp ===:\", temp)\n",
    "            for data in temp:\n",
    "                res.append(data)\n",
    "            print(\"*****:\", res)\n",
    "                    \n",
    "    print(\"processed:\", res)\n",
    "\n",
    "\n",
    "data1 = [10, 3, 7, 4, 12]\n",
    "data2 = [10, 2, 4, 5, 2, 6]\n",
    "# stack_increase(data1)\n",
    "stack_increase(data2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f719f1c1",
   "metadata": {},
   "source": [
    "### 1.3 具体试题\n",
    "- 单调栈： https://leetcode-cn.com/tag/monotonic-stack/problemset/"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a30f1c44",
   "metadata": {},
   "source": [
    "### 1.4 单调栈剖析\n",
    "- 刷题笔记6（浅谈单调栈）: https://zhuanlan.zhihu.com/p/26465701\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3ed95cd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
